#include "main/utils.h"
using namespace std;

bool isPalindrome(string str, int start, int end) {
  while (start < end) {
    if (str[start++] != str[end--]) {
      return false;
    }
  }
  return true;
}

void partitionCore(string str,
                   int index,
                   vector<string> result,
                   vector<vector<string>>& results) {
  if (index == str.size()) {
    results.push_back(result);
    return;
  }
  for (int i = index; i < str.size(); ++i) {
    if (isPalindrome(str, index, i)) {
      result.push_back(str.substr(index, i - index + 1));
      partitionCore(str, i + 1, result, results);
      result.pop_back();
    }
  }
}

vector<vector<string>> partition(const string& str) {
  vector<string> result;
  vector<vector<string>> results;
  partitionCore(str, 0, result, results);
  return results;
}

int main() {
  string str = "google";
  auto ret = partition(str);
  for (auto ele1 : ret) {
    for (auto ele2 : ele1) {
      cout << ele2 << endl;
    }
    cout << endl;
  }

  return 0;
}
